package ch2.app.link;

import java.io.PrintStream;
import java.util.*;
import java.io.FileInputStream;
import java.io.FileNotFoundException;

class PolyClass {   //多项式单链表类
    PolyElem head;  //存放多项式单链表头结点

    public PolyClass() {    //构造方法
        head = new PolyElem();  //建立头结点head
    }

    // 包含CreatePoly、Sort和DispPoly方法

    // 尾插法创建多项式
    public void CreatePoly(double[] coef, int[] exp, int n) {    //采用尾插法建立多项式单链表
        PolyElem s, t = head;       //t始终指向尾结点,开始时指向头结点
        for (int i = 0; i < n; i++) {
            s = new PolyElem(coef[i], exp[i]);   //创建新结点s
            t.next = s;     //在t结点之后插入s结点
            t = s;
        }
        t.next = null;      //尾结点next域置为null
    }

    // 根据指数倒序排序多项式
    public void Sort() {    //对多项式单链表按exp域递减排序
        PolyElem pre;   // 用于遍历有序单链表
        PolyElem q = head.next;              //q指向开始结点
        if (q == null) {
            return;                 //原单链表空返回
        }
        PolyElem p = head.next.next;         //p指向q结点的后继结点
        if (p == null) {
            return;                 //原单链表只有一个数据结点返回
        }
        // 将链表分成两部分：包含首结点的有序链表、p结点为首结点的单链表
        q.next = null;              //构造只含一个数据结点的有序单链表
        // 遍历p结点为首结点的单链表
        while (p != null) {
            q = p.next;             //q用于临时保存p结点后继结点
            pre = head;             //从有序表开头比较, pre指向插入结点p的前驱结点
            while (pre.next != null && pre.next.exp > p.exp) {
                pre = pre.next;     //在有序表中找插入结点p的前驱结点pre
            }
            p.next = pre.next;      //将pre结点之后插入p结点
            pre.next = p;
            p = q;                  //扫描原单链表余下的结点
        }
    }

    public void DispPoly() {    //输出多项式单链表
        boolean first = true;   //first为true表示是第一项
        PolyElem p = head.next;
        while (p != null) {
            if (first) {
                first = false;
            } else if (p.coef > 0) {
                System.out.print("+");
            }
            if (p.exp == 0) {   //指数为0时不输出'x'
                System.out.print(p.coef);
            } else if (p.exp == 1) {    //指数为1时不输出指数
                System.out.print(p.coef + "x");
            } else {
                System.out.print(p.coef + "x^" + p.exp);
            }
            p = p.next;
        }
        System.out.println();
    }
}

public class PolyTest1 {
    public static PolyClass Add(PolyClass L1, PolyClass L2) {   //两个多项式相加运算
        PolyElem p, q, s, t;    //t始终指向L3的尾结点
        double c;
        PolyClass L3 = new PolyClass();
        t = L3.head;
        p = L1.head.next;
        q = L2.head.next;
        while (p != null && q != null) {
            if (p.exp > q.exp) {    //L1的结点的指数较大
                s = new PolyElem(p.coef, p.exp);
                t.next = s;
                t = s;
                p = p.next;
            } else if (p.exp < q.exp) { //L2的结点的指数较大
                s = new PolyElem(q.coef, q.exp);
                t.next = s;
                t = s;
                q = q.next;
            } else {    //两结点的指数相等
                c = p.coef + q.coef;    //求两指数相等结点的系数和c
                if (c != 0) {           //系数和c不为0时复制
                    s = new PolyElem(c, p.exp);
                    t.next = s;
                    t = s;
                }
                p = p.next;
                q = q.next;
            }
        }
        t.next = null;  //尾结点next置为null
        if (p != null) {
            t.next = p;
        }else if (q != null) {
            t.next = q;
        }
        return L3;
    }

    public static void main(String[] args) throws FileNotFoundException {
        // 1. 重定向标准输入、输出流到abc.in、abc.out
        System.setIn(new FileInputStream("resource/ch2/abc.in"));
        Scanner fin = new Scanner(System.in);
        System.setOut(new PrintStream("resource/ch2/abc.out"));

        // 2. 初始化
        PolyClass L1 = new PolyClass();
        PolyClass L2 = new PolyClass();
        PolyClass L3;
        double[] a = new double[100];
        int[] b = new int[100];
        int n;

        // 3. 创建两个多项式
        n = fin.nextInt();              //输入第1个多项式的n
        for (int i = 0; i < n; i++) {   //输入第1个多项式系数数组a
            a[i] = fin.nextDouble();
        }
        for (int i = 0; i < n; i++) {   //输入第1个多项式指数数组b
            b[i] = fin.nextInt();
        }
        L1.CreatePoly(a, b, n);         //创建第1个多项式单链表
        System.out.print("第1个多项式:  ");
        L1.DispPoly();

        n = fin.nextInt();              //输入第2个多项式的n
        for (int i = 0; i < n; i++) {   //输入第2个多项式系数数组a
            a[i] = fin.nextDouble();
        }
        for (int i = 0; i < n; i++) {   //输入第2个多项式指数数组b
            b[i] = fin.nextInt();
        }
        L2.CreatePoly(a, b, n);         //创建第2个多项式单链表
        System.out.print("第2个多项式: ");
        L2.DispPoly();

        // 4. 两个多项式排序
        L1.Sort();                      //第1个多项式按指数递减排序
        System.out.print("L1排序后: ");
        L1.DispPoly();

        L2.Sort();                      //第2个多项式按指数递减排序
        System.out.print("L2排序后结果: ");
        L2.DispPoly();

        // 5. 两个多项式相加
        L3 = Add(L1, L2);               //两多项式相加
        System.out.print("多项式相加后: ");
        L3.DispPoly();
    }
}


// 设置abc.in的路径： System.setIn(new FileInputStream("./ch2/app/link/abc.in"));
// 打开Terminal，切换到src目录，运行以下命令
// javac -encoding utf8 .\ch2\app\link\PolyTest2.java
// java ch2.app.link.PolyTest2
